import java.util.Arrays;

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[] dist=new int[n+1];
        boolean[] st=new boolean[n+1];

        //将距离全部设置成无穷
        Arrays.fill(dist,0x3f3f3f3f);
        //k到k的距离是0
        dist[k]=0;

        int[][] matrix=new int[n+1][n+1];
        //将矩阵的距离也全部设置成无穷
        for(int[] x:matrix){
            Arrays.fill(x,0x3f3f3f3f);
        }
        //将距离录入矩阵,重边取最小
        for (int i = 0; i < times.length; i++) {
            matrix[times[i][0]][times[i][1]]=Math.min(times[i][2],matrix[times[i][0]][times[i][1]]);
        }

        for (int i = 0; i < n - 1; i++) {
            int t=-1;
            for (int j = 1; j <= n; j++) {
                if(!st[j] && (t==-1 || dist[t]>dist[j])){
                    t=j;
                }
            }
            st[t]=true;
            for (int j = 1; j <= n; j++) {
                dist[i]=Math.min(dist[i],dist[t]+matrix[t][i]);
            }
        }

        int max=-1;
        for (int i = 1; i <= n; i++) {
            max=Math.max(max,dist[i]);
        }

        if(max==0x3f3f3f3f){
            return -1;
        }
        return max;
    }
}